#include "graph.h"
#include <vector>
#include <queue>
#include <algorithm>
#include "assert.h"
#include <string>
#include <sstream>
#include <fstream>

using std::vector;
using std::queue;
using std::max;
using std::min;
using std::string;
using std::ostream;
using std::ofstream;
using std::endl;

bool biparate(const IGraph* const graph)
{
    vector<int> cols(graph->numVertecies(), -1);
    for(size_t i = 0; i < graph->numVertecies(); ++i) {
        if (cols[i] != -1) {
            continue;
        }
        queue<size_t> q;
        cols[i] = 0;
        q.push(i);
        while (!q.empty()) {
            size_t v = q.front();
            q.pop();
            const vector<size_t>& inc = graph->incendents(v);
            for(size_t j = 0; j < inc.size(); ++j) {
                if (cols[inc[j]] == -1) {
                    cols[inc[j]] = 1 - cols[v];
                    q.push(inc[j]);
                }
                if (cols[v] == cols[inc[j]]) {
                    return false;
                }
            }
        }
    }
    return true;
}

size_t naiveColoring(const IGraph* const graph, vector<int>& cols)
{
    size_t mind = cols.size();
    int minv = -1;
    for(size_t v = 0; v < cols.size(); ++v) {
        if (cols[v] == -1) {
            const vector<size_t>& inc = graph->incendents(v);
            size_t cd = 0;
            for(size_t i = 0; i < inc.size(); ++i) {
                if (cols[inc[i]] == -1) {
                    ++cd;
                }
            }
            if (cd < mind) {
                mind = cd;
                minv = v;
            }
        }
    }
    if (minv == -1) {
        return 0;
    }
    cols[minv] = -2;
    size_t res = naiveColoring(graph, cols);
    const vector<size_t>& inc = graph->incendents(minv);
    vector<int> ucols;
    for(size_t i = 0; i < inc.size(); ++i) {
        if (cols[inc[i]] != -2) {
            ucols.push_back(cols[inc[i]]);
        }
    }
    sort(ucols.begin(), ucols.end());
    ucols.erase(unique(ucols.begin(), ucols.end()), ucols.end());
    ucols.push_back(graph->numVertecies() + 10);
    assert(ucols[0] >= 0, "ucols[0] >= 0");
    for(size_t i = 0; i < graph->numVertecies(); ++i) {
        if (ucols[i] != (int)i) {
            cols[minv] = i;
            break;
        }
    }
    return max(res, (size_t)(cols[minv] + 1));
}

size_t naiveColoring(const IGraph* const graph)
{
    vector<int> cols(graph->numVertecies(), -1);
    size_t res = naiveColoring(graph, cols);
    size_t max_col = (size_t)cols[0];
    for(size_t i = 0; i < graph->numVertecies(); ++i) {
        max_col = max(max_col, (size_t)(cols[i]));
        const vector<size_t>& inc = graph->incendents(i);
        for(size_t j = 0; j < inc.size(); ++j) {
            assert(cols[i] != cols[inc[j]], "cols[i] != cols[inc[j]]");
        }
    }
    assert(res == max_col + 1, "res == max_col + 1");
    return res;
}

size_t runningNaiveColoring(const IGraph* const graph)
{
    vector<int> cols(graph->numVertecies(), -1);
    size_t res = 0;
    for(size_t v = 0; v < graph->numVertecies(); ++v) {
        const vector<size_t>& inc = graph->incendents(v);
        vector<int> ucols;
        for(size_t i = 0; i < inc.size(); ++i) {
            size_t u = inc[i];
            if (u < v && cols[u] != -1) {
                ucols.push_back(cols[u]);
            }
        }
        sort(ucols.begin(), ucols.end());
        ucols.erase(unique(ucols.begin(), ucols.end()), ucols.end());
        ucols.push_back(graph->numVertecies() + 10);
        assert(ucols[0] >= 0, "ucols[0] >= 0");
        for(size_t i = 0; i < graph->numVertecies(); ++i) {
            if (ucols[i] != (int)i) {
                cols[v] = i;
                break;
            }
        }
        res = max(res, (size_t)cols[v]);
        assert(cols[v] >= 0, "cols[v] >= 0");
    }
    for(size_t i = 0; i < graph->numVertecies(); ++i) {
        const vector<size_t>& inc = graph->incendents(i);
        for(size_t j = 0; j < inc.size(); ++j) {
            assert(cols[i] != cols[inc[j]], "cols[i] != cols[inc[j]]");
        }
    }
    return res;
}



bool correctColoring(const IGraph* const graph, vector<int>& cols, size_t v, size_t maxCol)
{
    if (maxCol > n + 1) {
        return false;
    }
	if (v >= cols.size()) {
        return maxCol <= n + 1;
    }
    size_t res = cols.size();
    vector<bool> uscols(res, false);
    for(size_t i = 0; i < v; ++i) {
        if (graph->isConnected(i, v) && cols[i] != -1) {
            uscols[cols[i]] = true;
        }
    }
    for(size_t i = 0; i < min(maxCol + 2, res); ++i) {
        if (!uscols[i]) {
            cols[v] = i;
    		if (correctColoring(graph, cols, v + 1, max(maxCol, (size_t)i))) {
	   	       	return true;
	       	}
        }
    }
    cols[v] = -1;
    return false;
}

bool correctColoring(const IGraph* const graph)
{
    vector<int> cols(graph->numVertecies(), -1);
    return correctColoring(graph, cols, 0, 0);
}

string visual(size_t v)
{
    string res;
    for(size_t i = 0; i < n; ++i) {
        int x = ((v & (1 << i)) != 0) + 2 * ((v & (1 << (i + n))) != 0);
        res += (char)('0' + x);
    }
    return res;
}

void draw(const IGraph* const graph, ostream& out)
{
    out << "graph graph_" << graph->name() << " {" << endl;
    for(size_t i = 0; i < graph->numVertecies(); ++i) {
        out << "" << visual(graph->vertex(i)) << ";" << endl;
    }
    for(size_t i = 0; i < graph->numVertecies(); ++i) {
        const vector<size_t>& cg = graph->incendents(i);
        for(size_t j = 0; j < cg.size(); ++j) {
            if (i < cg[j]) {
                out << visual(graph->vertex(i)) << " -- " << visual(graph->vertex(cg[j])) << ";\n";
            }
        }
    }
    out << "}\n";
}

void draw(const IGraph* const graph, string fname)
{
    ofstream out(fname.c_str());
    draw(graph, out);
}

size_t numEdges(const IGraph* const graph)
{
    size_t res = 0;
    for(size_t i = 0; i < graph->numVertecies(); ++i) {
    	res += graph->degree(i);
    }
    return res / 2;
}

void printInDIMACS(const IGraph* const graph, std::ostream& out)
{
	out << "p edges " << graph->numVertecies() <<  " " << numEdges(graph) << endl;
    for(size_t i = 0; i < graph->numVertecies(); ++i) {
        const vector<size_t>& cg = graph->incendents(i);
        for(size_t j = 0; j < cg.size(); ++j) {
            if (i < cg[j]) {
                out << "e " << 1 + i << " " << 1 + cg[j] << "\n";
            }
        }
    }
}

GraphC *convertToGraphC(const IGraph* const graph)
{
    GraphC *g;
    g=createGraph(graph->numVertecies(), numEdges(graph));
    initNodes(graph->numVertecies(),g);
                  
    for(size_t i = 0; i < graph->numVertecies(); ++i) {
        const vector<size_t>& cg = graph->incendents(i);
        for(size_t j = 0; j < cg.size(); ++j) {
            int w = i + 1, v = cg[j] + 1;
            Node *nW, *nV;
            nW=getNodeFromList(w,g->nodesList);
            nV=getNodeFromList(v,g->nodesList);
            appendpNodesList(nW,nV->adj);
            nV->numAdj++;
        }
    }
  return g;
}


